package Tree;

public class p106从中序与后序遍历序列构造二叉树 {
    class Solution {
        public TreeNode buildTree(int[] inorder, int[] postorder) {
            // 后序数组最后一个元素的值即为根节点的值
            int rootValue = postorder[postorder.length - 1];
            TreeNode root = new TreeNode(rootValue);
            if (postorder.length == 1) return root;
            // 拿到根节点的值后遍历中序数组，找到划分点index
            int index;
            for (index = 0; index < inorder.length; index++) {
                if (rootValue == inorder[index]) break;
            }

            // 根据划分点index分割中序数组和后序数组
            int[] leftInorder = new int[index];
            System.arraycopy(inorder, 0, leftInorder, 0, index);
            int[] rightInorder = new int[inorder.length - index - 1];
            for (int i = 0; i < inorder.length - index - 1; i++) {
                rightInorder[i] = inorder[i + index + 1];
            }

            int[] leftPostorder = new int[index];
            System.arraycopy(postorder, 0, leftPostorder, 0, index);
            int[] rightPostorder = new int[rightInorder.length];
            System.arraycopy(postorder, index, rightPostorder, 0, rightPostorder.length);
            // 根据划分后的数组递归
            root.left = buildTree(leftInorder, leftPostorder);
            root.right = buildTree(rightInorder, rightPostorder);

            return root;
        }
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
